<!DOCTYPE html>
<html lang="zh">
    <head>
    <!--
        © Material Theme
        https://github.com/viosey/hexo-theme-material
        Version: 1.3.0 -->

    <!-- Title -->
    
    <title>
        
            JDK底层实现源码分析系列(四) HashMap源码分析 | 
        
        Binux Blog
    </title>

    <!-- Favicons -->
    <link rel="icon shortcut" type="image/ico" href="http://on2bs9q7q.bkt.clouddn.com/avatar.png">
    <link rel="icon" sizes="192x192" href="http://on2bs9q7q.bkt.clouddn.com/favicon.png">
    <link rel="apple-touch-icon" href="http://on2bs9q7q.bkt.clouddn.com/favicon.png">

    <!-- Meta & Info -->
    <meta charset="utf-8">
    <meta http-equiv="X-UA-Compatible">
    <meta name="viewport" content="width=device-width, initial-scale=1">
    <meta name="theme-color" content="#0097A7">
    <meta name="author" content="Binux">
    <meta name="description" content="一名正在崛起的Java后端工程师">
    <meta name="keywords" content="null,JDK,Source Code">

    <!--iOS -->
    <meta name="viewport" content="width=device-width, initial-scale=1, user-scalable=no">
    <meta name="apple-mobile-web-app-title" content="Title">
    <meta name="apple-mobile-web-app-capable" content="yes">
    <meta name="apple-mobile-web-app-status-bar-style" content="black">
    <meta name="HandheldFriendly" content="True">
    <meta name="MobileOptimized" content="480">

    <!-- Add to homescreen for Chrome on Android -->
    <meta name="mobile-web-app-capable" content="yes">

    <!-- Add to homescreen for Safari on iOS -->
    <meta name="apple-mobile-web-app-capable" content="yes">
    <meta name="apple-mobile-web-app-status-bar-style" content="black">
    <meta name="apple-mobile-web-app-title" content="Binux Blog">

    <!-- The Open Graph protocol -->
    <meta property="og:url" content="http://binux.cn">
    <meta property="og:type" content="blog">
    <meta property="og:title" content="JDK底层实现源码分析系列(四) HashMap源码分析 | Binux Blog">
    <meta property="og:description" content="一名正在崛起的Java后端工程师">
    <meta property="og:article:tag" content="JDK"> <meta property="og:article:tag" content="Source Code"> 

    <!--[if lte IE 9]>
        <link rel="stylesheet" href="/css/ie-blocker.css">

        
            <script src="/js/ie-blocker.zhCN.js"></script>
        
    <![endif]-->

    <!-- Import CSS -->
    <link rel="stylesheet" href="/css/material.min.css">
    <link rel="stylesheet" href="/css/style.min.css">
    <!-- Config CSS -->


<!-- Other Styles -->
<style>
  body, html {
    font-family: Roboto, "Helvetica Neue", Helvetica, "PingFang SC", "Hiragino Sans GB", "Microsoft YaHei", "微软雅黑", Arial, sans-serif;
  }

  a {
    color: #00838F;
  }

  .mdl-card__media,
  #search-label,
  #search-form-label:after,
  #scheme-Paradox .hot_tags-count,
  #scheme-Paradox .sidebar_archives-count,
  #scheme-Paradox .sidebar-colored .sidebar-header,
  #scheme-Paradox .sidebar-colored .sidebar-badge{
    background-color: #0097A7 !important;
  }

  /* Sidebar User Drop Down Menu Text Color */
  #scheme-Paradox .sidebar-colored .sidebar-nav>.dropdown>.dropdown-menu>li>a:hover,
  #scheme-Paradox .sidebar-colored .sidebar-nav>.dropdown>.dropdown-menu>li>a:focus {
    color: #0097A7 !important;
  }

  #post_entry-right-info,
  .sidebar-colored .sidebar-nav li:hover > a,
  .sidebar-colored .sidebar-nav li:hover > a i,
  .sidebar-colored .sidebar-nav li > a:hover,
  .sidebar-colored .sidebar-nav li > a:hover i,
  .sidebar-colored .sidebar-nav li > a:focus i,
  .sidebar-colored .sidebar-nav > .open > a,
  .sidebar-colored .sidebar-nav > .open > a:hover,
  .sidebar-colored .sidebar-nav > .open > a:focus,
  #ds-reset #ds-ctx .ds-ctx-entry .ds-ctx-head a {
    color: #0097A7 !important;
  }

  .toTop {
    background: #757575 !important;
  }

  .material-layout .material-post>.material-nav,
  .material-layout .material-index>.material-nav,
  .material-nav a {
    color: #757575;
  }

  #scheme-Paradox .MD-burger-layer {
    background-color: #757575;
  }

  #scheme-Paradox #post-toc-trigger-btn {
    color: #757575;
  }

  .post-toc a:hover {
    color: #00838F;
    text-decoration: underline;
  }
</style>


<!-- Theme Background Related-->

    <style>
      body{
        background-color: #F5F5F5;
      }

      /* blog_info bottom background */
      #scheme-Paradox .material-layout .something-else .mdl-card__supporting-text{
        background-color: #fff;
      }
    </style>




<!-- Fade Effect -->

    <style>
      .fade {
        transition: all 800ms linear;
        -webkit-transform: translate3d(0,0,0);
        -moz-transform: translate3d(0,0,0);
        -ms-transform: translate3d(0,0,0);
        -o-transform: translate3d(0,0,0);
        transform: translate3d(0,0,0);
        opacity: 1;
      }

      .fade.out{
        opacity: 0;
      }
    </style>



    <script src="/js/jquery.min.js"></script>
    <script src="/js/queue.js"></script>

    <!-- UC Browser Compatible -->
    <script>
        var agent = navigator.userAgent.toLowerCase();
        if(agent.indexOf('ucbrowser')>0) {
            document.write("<link rel=\"stylesheet\" href=\"/css/uc.css\">");
            alert('由于 UC 浏览器使用极旧的内核，而本网站使用了一些新的特性。\n为了您能更好的浏览，推荐使用 Chrome 或 Firefox 浏览器。');
        }
    </script>

    
    <!-- Baidu Analytics -->
    <script>
        var _hmt = _hmt || [];
        (function() {var hm = document.createElement('script');
        hm.src = 'https://hm.baidu.com/hm.js?c286c0c5e31950b803d5d56c74493f58';
        var s = document.getElementsByTagName('script')[0];
        s.parentNode.insertBefore(hm, s);
        })();
    </script>
    

    
    <!-- Google Analytics -->
    <script>
        (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
        (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
        m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
        })(window,document,'script','https://www.google-analytics.com/analytics.js','ga');
        ga('create', 'UA-92760839-1', 'auto');ga('send', 'pageview');
    </script>
    

    <!-- Bing Background -->
    

    <!-- Custom Head -->
    
</head>


    
        <body id="scheme-Paradox" class="lazy">
            <div class="material-layout  mdl-js-layout has-drawer is-upgraded">
                

                <!-- Main Container -->
                <main class="material-layout__content" id="main">

                    <!-- Top Anchor -->
                    <div id="top"></div>

                    
                        <!-- Hamburger Button -->
                        <button class="MD-burger-icon sidebar-toggle">
                            <span class="MD-burger-layer"></span>
                        </button>
                    

                    <!-- Post TOC -->

    
    <!-- Back Button -->
    <!--
    <div class="material-back" id="backhome-div" tabindex="0">
        <a class="mdl-button mdl-js-button mdl-js-ripple-effect mdl-button--icon"
           href="#" onclick="window.history.back();return false;"
           target="_self"
           role="button"
           data-upgraded=",MaterialButton,MaterialRipple">
            <i class="material-icons" role="presentation">arrow_back</i>
            <span class="mdl-button__ripple-container">
                <span class="mdl-ripple"></span>
            </span>
        </a>
    </div>
    -->

    <!-- Left aligned menu below button -->
    <button id="post-toc-trigger-btn"
        class="mdl-button mdl-js-button mdl-button--icon">
        <i class="material-icons">format_list_numbered</i>
    </button>

    <ul class="post-toc-wrap mdl-menu mdl-menu--bottom-left mdl-js-menu mdl-js-ripple-effect" for="post-toc-trigger-btn">
        <ol class="post-toc"><li class="post-toc-item post-toc-level-2"><a class="post-toc-link" href="#前言"><span class="post-toc-number">1.</span> <span class="post-toc-text">前言</span></a><ol class="post-toc-child"><li class="post-toc-item post-toc-level-3"><a class="post-toc-link" href="#Collection-大家族"><span class="post-toc-number">1.1.</span> <span class="post-toc-text">Collection 大家族</span></a></li><li class="post-toc-item post-toc-level-3"><a class="post-toc-link" href="#LinkedList-继承树"><span class="post-toc-number">1.2.</span> <span class="post-toc-text">LinkedList 继承树</span></a></li></ol></li><li class="post-toc-item post-toc-level-2"><a class="post-toc-link" href="#分析"><span class="post-toc-number">2.</span> <span class="post-toc-text">分析</span></a><ol class="post-toc-child"><li class="post-toc-item post-toc-level-3"><a class="post-toc-link" href="#概述"><span class="post-toc-number">2.1.</span> <span class="post-toc-text">概述</span></a></li><li class="post-toc-item post-toc-level-3"><a class="post-toc-link" href="#成员变量"><span class="post-toc-number">2.2.</span> <span class="post-toc-text">成员变量</span></a></li><li class="post-toc-item post-toc-level-3"><a class="post-toc-link" href="#构造方法"><span class="post-toc-number">2.3.</span> <span class="post-toc-text">构造方法</span></a></li><li class="post-toc-item post-toc-level-3"><a class="post-toc-link" href="#内部类"><span class="post-toc-number">2.4.</span> <span class="post-toc-text">内部类</span></a></li><li class="post-toc-item post-toc-level-3"><a class="post-toc-link" href="#存储"><span class="post-toc-number">2.5.</span> <span class="post-toc-text">存储</span></a></li><li class="post-toc-item post-toc-level-3"><a class="post-toc-link" href="#查找数据"><span class="post-toc-number">2.6.</span> <span class="post-toc-text">查找数据</span></a></li><li class="post-toc-item post-toc-level-3"><a class="post-toc-link" href="#扩容机制"><span class="post-toc-number">2.7.</span> <span class="post-toc-text">扩容机制</span></a></li><li class="post-toc-item post-toc-level-3"><a class="post-toc-link" href="#fail-fast机制"><span class="post-toc-number">2.8.</span> <span class="post-toc-text">fail-fast机制</span></a></li><li class="post-toc-item post-toc-level-3"><a class="post-toc-link" href="#遍历方式"><span class="post-toc-number">2.9.</span> <span class="post-toc-text">遍历方式</span></a></li></ol></li><li class="post-toc-item post-toc-level-2"><a class="post-toc-link" href="#总结"><span class="post-toc-number">3.</span> <span class="post-toc-text">总结</span></a></li><li class="post-toc-item post-toc-level-2"><a class="post-toc-link" href="#著作权声明"><span class="post-toc-number">4.</span> <span class="post-toc-text">著作权声明</span></a></li></ol>

        <!--
        <li class="mdl-menu__item">
            Some Action
        </li>
        -->
    </ul>




<!-- Layouts -->

    <!-- Post Module -->
    <div class="material-post_container">

        <div class="material-post mdl-grid">
            <div class="mdl-card mdl-shadow--4dp mdl-cell mdl-cell--12-col">

                <!-- Post Header(Thumbnail & Title) -->
                
    <!-- Paradox Post Header -->
    
        <!-- Custom Thumbnail -->
        <div class="post_thumbnail-custom mdl-card__media mdl-color-text--grey-50" style="background-image:url(http://on2bs9q7q.bkt.clouddn.com/HashMap.jpg)">
    
            <p class="article-headline-p">
                JDK底层实现源码分析系列(四) HashMap源码分析
            </p>
        </div>





                
                    <!-- Paradox Post Info -->
                    <div class="mdl-color-text--grey-700 mdl-card__supporting-text meta">

    <!-- Author Avatar -->
    <div id="author-avatar">
        <img src="http://on2bs9q7q.bkt.clouddn.com/avatar.jpg" width="44px" height="44px" alt="Author Avatar"/>
    </div>
    <!-- Author Name & Date -->
    <div>
        <strong>Binux</strong>
        <span>3月 14, 2017</span>
    </div>

    <div class="section-spacer"></div>

    <!-- Favorite -->
    <!--
        <button id="article-functions-like-button" class="mdl-button mdl-js-button mdl-js-ripple-effect mdl-button--icon btn-like">
            <i class="material-icons" role="presentation">favorite</i>
            <span class="visuallyhidden">favorites</span>
        </button>
    -->

    <!-- Qrcode -->
    
        <button id="article-functions-qrcode-button" class="mdl-button mdl-js-button mdl-js-ripple-effect mdl-button--icon">
            <i class="material-icons" role="presentation">devices other</i>
            <span class="visuallyhidden">devices other</span>
        </button>
        <ul class="mdl-menu mdl-menu--bottom-right mdl-js-menu mdl-js-ripple-effect" for="article-functions-qrcode-button">
            <li class="mdl-menu__item">在其它设备中阅读本文章</li>
            <img src="">
        </ul>
    

    <!-- Tags (bookmark) -->
    
    <button id="article-functions-viewtags-button" class="mdl-button mdl-js-button mdl-js-ripple-effect mdl-button--icon">
        <i class="material-icons" role="presentation">bookmark</i>
        <span class="visuallyhidden">bookmark</span>
    </button>
    <ul class="mdl-menu mdl-menu--bottom-right mdl-js-menu mdl-js-ripple-effect" for="article-functions-viewtags-button">
        <li class="mdl-menu__item">
        <a class="post_tag-link" href="/tags/JDK/">JDK</a></li><li class="mdl-menu__item"><a class="post_tag-link" href="/tags/Source-Code/">Source Code</a>
    </ul>
    

    <!-- Share -->
    <button id="article-fuctions-share-button" class="mdl-button mdl-js-button mdl-js-ripple-effect mdl-button--icon">
    <i class="material-icons" role="presentation">share</i>
    <span class="visuallyhidden">share</span>
</button>
<ul class="mdl-menu mdl-menu--bottom-right mdl-js-menu mdl-js-ripple-effect" for="article-fuctions-share-button">
    

    
        
            <!-- Busuanzi Views -->
            <a class="post_share-link" href="#">
                <li class="mdl-menu__item">
                    <span id="busuanzi_container_page_pv">
                        <span id="busuanzi_value_page_pv"></span>&nbsp;浏览量
                    </span>
                </li>
            </a>
        
    

    <!-- Share Weibo -->
    
        <a class="post_share-link" href="http://service.weibo.com/share/share.php?appkey=&title=JDK底层实现源码分析系列(四) HashMap源码分析&url=http://binux.cn//2017/03/14/HastMap-Source-Code/index.html&pic=&searchPic=false&style=simple" target="_blank">
            <li class="mdl-menu__item">
                分享到微博
            </li>
        </a>
    

    <!-- Share Twitter -->
    

    <!-- Share Facebook -->
    

    <!-- Share Google+ -->
    
        <a class="post_share-link" href="https://plus.google.com/share?url=http://binux.cn//2017/03/14/HastMap-Source-Code/index.html" target="_blank">
            <li class="mdl-menu__item">
                分享到 Google+
            </li>
        </a>
    

    <!-- Share LinkedIn -->
    

    <!-- Share QQ -->
    
        <a class="post_share-link" href="http://connect.qq.com/widget/shareqq/index.html?site=Binux Blog&title=JDK底层实现源码分析系列(四) HashMap源码分析&summary=一名正在崛起的Java后端工程师&pics=http://binux.cnhttp://on2bs9q7q.bkt.clouddn.com/avatar.png&url=http://binux.cn/2017/03/14/HastMap-Source-Code/index.html" target="_blank">
            <li class="mdl-menu__item">
                分享到 QQ
            </li>
        </a>
    

    <!-- Share Telegram -->
    
</ul>

</div>

                

                <!-- Post Content -->
                <div id="post-content" class="mdl-color-text--grey-700 mdl-card__supporting-text fade out">
    
        <blockquote>
<p>“合抱之木 生于毫末 九层之台 起于累土 千里之行 始于足下”</p>
</blockquote>
<h2 id="前言"><a href="#前言" class="headerlink" title="前言"></a>前言</h2><blockquote>
<p>JDK 版本1.7<br>注:JDK1.8对HashMap进行重构 引入了红黑树 大幅优化HashMap的查找速度</p>
</blockquote>
<h3 id="Collection-大家族"><a href="#Collection-大家族" class="headerlink" title="Collection 大家族"></a>Collection 大家族</h3><center><img src="http://on2bs9q7q.bkt.clouddn.com/Java-Collections.png" alt="Collection"></center>

<blockquote>
<p>来源<a href="https://infinitescript.com/2014/10/java-collections-framework/" target="_blank" rel="external">Java Collections Framework</a></p>
</blockquote>
<h3 id="LinkedList-继承树"><a href="#LinkedList-继承树" class="headerlink" title="LinkedList 继承树"></a>LinkedList 继承树</h3><center><img src="http://on2bs9q7q.bkt.clouddn.com/HashMap.png" alt="Stack"></center><br><center>HashMap</center>



<hr>
<h2 id="分析"><a href="#分析" class="headerlink" title="分析"></a>分析</h2><h3 id="概述"><a href="#概述" class="headerlink" title="概述"></a>概述</h3><p>HashMap是基于哈希表,实现Map接口的非同步集合,允许使用Null键和Null值,但是不保证映射的顺序，特别是他不保证集合中的顺序恒久不变</p>
<p>内部维护着一个数组用来存放数据,并且每个数组的元素都是一个单向链表</p>
<center><img src="http://on2bs9q7q.bkt.clouddn.com/HashMap-Array.png" alt="Stack"></center><br><center>HaspMap底层存储结构</center>

<p>使用<code>get()</code>获取数据<code>put()</code>存放数据,内部基于hash算法会尽可能的将元素分布均匀在数组中</p>
<p>在查找元素时先计算hash值,因为对同一个对象取hash值返回的都是相同的,用hash值去取模数组的长度就可以快速获取那一条链表</p>
<p>但是求余操作本身也是一种高耗费的操作, 所以HashMap的size会通过算法永远为2的n次方, 可以利用位操作来高效实现求余。要找到数组中当前序号指向的元素，可以通过mod操作，<code>hash mod array length = array index</code>，优化后可以通过：<code>hash &amp; （array length－1） = array index</code>实现。比如一共有16个，<code>3&amp;（16－1）=3</code>，HashMap就是用这个方式来定位数组元素的，这种方式比取模的速度更快。</p>
<h3 id="成员变量"><a href="#成员变量" class="headerlink" title="成员变量"></a>成员变量</h3><figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div><div class="line">30</div><div class="line">31</div><div class="line">32</div><div class="line">33</div><div class="line">34</div><div class="line">35</div><div class="line">36</div><div class="line">37</div><div class="line">38</div><div class="line">39</div><div class="line">40</div><div class="line">41</div><div class="line">42</div><div class="line">43</div><div class="line">44</div><div class="line">45</div><div class="line">46</div><div class="line">47</div><div class="line">48</div><div class="line">49</div><div class="line">50</div><div class="line">51</div><div class="line">52</div></pre></td><td class="code"><pre><div class="line"><span class="comment">/**</span></div><div class="line">   * 默认容量</div><div class="line">   */</div><div class="line">  <span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">int</span> DEFAULT_INITIAL_CAPACITY = <span class="number">1</span> &lt;&lt; <span class="number">4</span>; <span class="comment">// aka 16</span></div><div class="line"></div><div class="line">  <span class="comment">/**</span></div><div class="line">   * 最大容量 1073741824</div><div class="line">   */</div><div class="line">  <span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">int</span> MAXIMUM_CAPACITY = <span class="number">1</span> &lt;&lt; <span class="number">30</span>;</div><div class="line"></div><div class="line">  <span class="comment">/**</span></div><div class="line">   * 默认加载系数</div><div class="line">   */</div><div class="line">  <span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">float</span> DEFAULT_LOAD_FACTOR = <span class="number">0.75f</span>;</div><div class="line"></div><div class="line">  <span class="comment">/**</span></div><div class="line">   * An empty table instance to share when the table is not inflated.</div><div class="line">   */</div><div class="line">  <span class="keyword">static</span> <span class="keyword">final</span> Entry&lt;?,?&gt;[] EMPTY_TABLE = &#123;&#125;;</div><div class="line"></div><div class="line">  <span class="comment">/**</span></div><div class="line">   * Entry类型的数组 实际上为一个链表</div><div class="line">   */</div><div class="line">  <span class="keyword">transient</span> Entry&lt;K,V&gt;[] table = (Entry&lt;K,V&gt;[]) EMPTY_TABLE;</div><div class="line"></div><div class="line">  <span class="comment">/**</span></div><div class="line">   * map的大小</div><div class="line">   */</div><div class="line">  <span class="keyword">transient</span> <span class="keyword">int</span> size;</div><div class="line"></div><div class="line">  <span class="comment">/**</span></div><div class="line">   * HashMap的容量阈值 当threshold="容量*系数"时HashMap就会增加容量</div><div class="line">   * <span class="doctag">@serial</span></div><div class="line">   */</div><div class="line">  <span class="keyword">int</span> threshold;</div><div class="line"></div><div class="line">  <span class="comment">/**</span></div><div class="line">   * 加载系数</div><div class="line">   *</div><div class="line">   * <span class="doctag">@serial</span></div><div class="line">   */</div><div class="line">  <span class="keyword">final</span> <span class="keyword">float</span> loadFactor;</div><div class="line"></div><div class="line">  <span class="comment">/**</span></div><div class="line">   * 实现fail-fast机制</div><div class="line">   */</div><div class="line">  <span class="keyword">transient</span> <span class="keyword">int</span> modCount;</div><div class="line"></div><div class="line">  <span class="comment">/**</span></div><div class="line">   * int最大值</div><div class="line">   */</div><div class="line">  <span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">int</span> ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;</div></pre></td></tr></table></figure>
<h3 id="构造方法"><a href="#构造方法" class="headerlink" title="构造方法"></a>构造方法</h3><p>HashMap一共有四个构造方法</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div><div class="line">30</div><div class="line">31</div><div class="line">32</div><div class="line">33</div><div class="line">34</div><div class="line">35</div><div class="line">36</div><div class="line">37</div><div class="line">38</div><div class="line">39</div><div class="line">40</div><div class="line">41</div><div class="line">42</div><div class="line">43</div><div class="line">44</div><div class="line">45</div><div class="line">46</div><div class="line">47</div><div class="line">48</div><div class="line">49</div><div class="line">50</div><div class="line">51</div><div class="line">52</div><div class="line">53</div></pre></td><td class="code"><pre><div class="line"><span class="comment">/**</span></div><div class="line"> * 构造一个空的HashMap使用默认的容量16和默认的加载系数0.75</div><div class="line"> *</div><div class="line"> */</div><div class="line"><span class="function"><span class="keyword">public</span> <span class="title">HashMap</span><span class="params">()</span> </span>&#123;</div><div class="line">    <span class="keyword">this</span>(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="comment">/**</span></div><div class="line"> * 构造一个空的HashMap使用指定容量,默认的加载系数0.75</div><div class="line"> *</div><div class="line"> * <span class="doctag">@param</span>  initialCapacity 指定容量</div><div class="line"> * <span class="doctag">@throws</span> IllegalArgumentException</div><div class="line"> */</div><div class="line"><span class="function"><span class="keyword">public</span> <span class="title">HashMap</span><span class="params">(<span class="keyword">int</span> initialCapacity)</span> </span>&#123;</div><div class="line">    <span class="keyword">this</span>(initialCapacity, DEFAULT_LOAD_FACTOR);</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="comment">/**</span></div><div class="line"> * 构造一个空的HashMap使用指定容量和加载系数</div><div class="line"> *</div><div class="line"> * <span class="doctag">@param</span>  initialCapacity 指定容量</div><div class="line"> * <span class="doctag">@param</span>  loadFactor      加载系数</div><div class="line"> * <span class="doctag">@throws</span> IllegalArgumentException</div><div class="line"> */</div><div class="line"><span class="function"><span class="keyword">public</span> <span class="title">HashMap</span><span class="params">(<span class="keyword">int</span> initialCapacity, <span class="keyword">float</span> loadFactor)</span> </span>&#123;</div><div class="line">    <span class="keyword">if</span> (initialCapacity &lt; <span class="number">0</span>)</div><div class="line">        <span class="keyword">throw</span> <span class="keyword">new</span> IllegalArgumentException(<span class="string">"Illegal initial capacity: "</span> +</div><div class="line">                                           initialCapacity);</div><div class="line">    <span class="keyword">if</span> (initialCapacity &gt; MAXIMUM_CAPACITY)</div><div class="line">        initialCapacity = MAXIMUM_CAPACITY;</div><div class="line">    <span class="keyword">if</span> (loadFactor &lt;= <span class="number">0</span> || Float.isNaN(loadFactor))</div><div class="line">        <span class="keyword">throw</span> <span class="keyword">new</span> IllegalArgumentException(<span class="string">"Illegal load factor: "</span> +</div><div class="line">                                           loadFactor);</div><div class="line"></div><div class="line">    <span class="keyword">this</span>.loadFactor = loadFactor;</div><div class="line">    threshold = initialCapacity;</div><div class="line">    init();</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="comment">/**</span></div><div class="line"> * 构造一个空的HashMap并把m的数据全部放入</div><div class="line"> *</div><div class="line"> * <span class="doctag">@param</span>   m 指定map</div><div class="line"> * <span class="doctag">@throws</span>  NullPointerException</div><div class="line"> */</div><div class="line"><span class="function"><span class="keyword">public</span> <span class="title">HashMap</span><span class="params">(Map&lt;? extends K, ? extends V&gt; m)</span> </span>&#123;</div><div class="line">    <span class="keyword">this</span>(Math.max((<span class="keyword">int</span>) (m.size() / DEFAULT_LOAD_FACTOR) + <span class="number">1</span>,</div><div class="line">                  DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);</div><div class="line">    inflateTable(threshold);</div><div class="line"></div><div class="line">    putAllForCreate(m);</div><div class="line">&#125;</div></pre></td></tr></table></figure>
<h3 id="内部类"><a href="#内部类" class="headerlink" title="内部类"></a>内部类</h3><p>HashMap的内部类非常多,一共有9个,基本上都是用来遍历集合的,但是有个内部类非常重要<code>Entry</code>他是整个HashMap存储元素的对象,基本上所有的方法都会使用到他</p>
<ul>
<li>static class Entry<k,v> implements Map.Entry<k,v></k,v></k,v></li>
<li>private final class EntryIterator extends HashIterator<map.entry<k,v>&gt;</map.entry<k,v></li>
<li>private final class EntrySet extends AbstractSet<map.entry<k,v>&gt;</map.entry<k,v></li>
<li>private abstract class HashIterator<e> implements Iterator<e></e></e></li>
<li>private static class Holder</li>
<li>private final class KeyIterator extends HashIterator<k></k></li>
<li>private final class KeySet extends AbstractSet<k></k></li>
<li>private final class ValueIterator extends HashIterator<v></v></li>
<li>private final class Values extends AbstractCollection<v></v></li>
</ul>
<h3 id="存储"><a href="#存储" class="headerlink" title="存储"></a>存储</h3><p>存储元素时调用<code>put(K key, V value)</code>调用<code>addEntry(int hash, K key, V value, int bucketIndex)</code>调用<code>createEntry(int hash, K key, V value, int bucketIndex)</code>进行插入元素</p>
<p>前面所说的取模优化就在<code>put()</code>代码的第13行,下面代码则保证HashMap的容量始终为2的指数幂</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div></pre></td><td class="code"><pre><div class="line"><span class="function"><span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">int</span> <span class="title">roundUpToPowerOf2</span><span class="params">(<span class="keyword">int</span> number)</span> </span>&#123;</div><div class="line">    <span class="comment">// assert number &gt;= 0 : "number must be non-negative";</span></div><div class="line">    <span class="keyword">return</span> number &gt;= MAXIMUM_CAPACITY</div><div class="line">            ? MAXIMUM_CAPACITY</div><div class="line">            : (number &gt; <span class="number">1</span>) ? Integer.highestOneBit((number - <span class="number">1</span>) &lt;&lt; <span class="number">1</span>) : <span class="number">1</span>;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
<blockquote>
<p>之所以调用这么多次是因为考虑到让子类继承/实现HashMap可以重写方法实现自己的特点操作</p>
</blockquote>
<figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div><div class="line">30</div><div class="line">31</div><div class="line">32</div><div class="line">33</div><div class="line">34</div><div class="line">35</div><div class="line">36</div><div class="line">37</div><div class="line">38</div><div class="line">39</div><div class="line">40</div><div class="line">41</div><div class="line">42</div><div class="line">43</div><div class="line">44</div><div class="line">45</div><div class="line">46</div><div class="line">47</div><div class="line">48</div><div class="line">49</div><div class="line">50</div><div class="line">51</div><div class="line">52</div><div class="line">53</div><div class="line">54</div><div class="line">55</div><div class="line">56</div><div class="line">57</div><div class="line">58</div><div class="line">59</div><div class="line">60</div><div class="line">61</div><div class="line">62</div><div class="line">63</div><div class="line">64</div><div class="line">65</div><div class="line">66</div><div class="line">67</div><div class="line">68</div><div class="line">69</div></pre></td><td class="code"><pre><div class="line"><span class="comment">/**</span></div><div class="line"> * 在map中插入指定key-value</div><div class="line"> * 如果之前的map中包含此key,则替换他</div><div class="line"> *</div><div class="line"> */</div><div class="line"><span class="function"><span class="keyword">public</span> V <span class="title">put</span><span class="params">(K key, V value)</span> </span>&#123;</div><div class="line">    <span class="keyword">if</span> (table == EMPTY_TABLE) &#123;</div><div class="line">        inflateTable(threshold); <span class="comment">// 扩容2倍</span></div><div class="line">    &#125;</div><div class="line">    <span class="keyword">if</span> (key == <span class="keyword">null</span>)</div><div class="line">        <span class="keyword">return</span> putForNullKey(value); <span class="comment">// 允许key为null插入value</span></div><div class="line">    <span class="keyword">int</span> hash = hash(key); <span class="comment">// 计算hash</span></div><div class="line">    <span class="keyword">int</span> i = indexFor(hash, table.length); <span class="comment">// 获取数组的index （hash &amp; (table.length-1);）</span></div><div class="line">    <span class="keyword">for</span> (Entry&lt;K,V&gt; e = table[i]; e != <span class="keyword">null</span>; e = e.next) &#123; <span class="comment">// 遍历链表</span></div><div class="line">        Object k;</div><div class="line">        <span class="keyword">if</span> (e.hash == hash &amp;&amp; ((k = e.key) == key || key.equals(k))) &#123; <span class="comment">// 存在此key</span></div><div class="line">            V oldValue = e.value;</div><div class="line">            e.value = value;</div><div class="line">            e.recordAccess(<span class="keyword">this</span>);</div><div class="line">            <span class="keyword">return</span> oldValue; <span class="comment">// 返回替换value</span></div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    modCount++;</div><div class="line">    addEntry(hash, key, value, i); <span class="comment">// 无此key 添加元素i为数组索引</span></div><div class="line">    <span class="keyword">return</span> <span class="keyword">null</span>;</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="comment">/**</span></div><div class="line"> * 在指定数组index位置的链表最后插入新节点</div><div class="line"> *</div><div class="line"> * Subclass overrides this to alter the behavior of put method.</div><div class="line"> */</div><div class="line"><span class="function"><span class="keyword">void</span> <span class="title">addEntry</span><span class="params">(<span class="keyword">int</span> hash, K key, V value, <span class="keyword">int</span> bucketIndex)</span> </span>&#123;</div><div class="line">    <span class="keyword">if</span> ((size &gt;= threshold) &amp;&amp; (<span class="keyword">null</span> != table[bucketIndex])) &#123; <span class="comment">// 扩容数组</span></div><div class="line">        resize(<span class="number">2</span> * table.length);</div><div class="line">        hash = (<span class="keyword">null</span> != key) ? hash(key) : <span class="number">0</span>;</div><div class="line">        bucketIndex = indexFor(hash, table.length);</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    createEntry(hash, key, value, bucketIndex); <span class="comment">// 真正新建节点的方法</span></div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="comment">/**</span></div><div class="line"> * 新建链表节点</div><div class="line"> */</div><div class="line"><span class="function"><span class="keyword">void</span> <span class="title">createEntry</span><span class="params">(<span class="keyword">int</span> hash, K key, V value, <span class="keyword">int</span> bucketIndex)</span> </span>&#123;</div><div class="line">    Entry&lt;K,V&gt; e = table[bucketIndex]; <span class="comment">// 直接定位 获取bucketIndex节点</span></div><div class="line">    table[bucketIndex] = <span class="keyword">new</span> Entry&lt;&gt;(hash, key, value, e);</div><div class="line">    <span class="comment">// 新建节点放入bucketIndex节点 并让其内部下个节点指向原来的节点</span></div><div class="line">    size++; <span class="comment">// 容量加1</span></div><div class="line">&#125;</div><div class="line"><span class="comment">/**</span></div><div class="line"> * 根据对象计算hash值 此算法加入了高位计算，防止地位不变，高位变话时造成的hash冲突</div><div class="line"> */</div><div class="line"><span class="function"><span class="keyword">final</span> <span class="keyword">int</span> <span class="title">hash</span><span class="params">(Object k)</span> </span>&#123;</div><div class="line">    <span class="keyword">int</span> h = hashSeed;</div><div class="line">    <span class="keyword">if</span> (<span class="number">0</span> != h &amp;&amp; k <span class="keyword">instanceof</span> String) &#123;</div><div class="line">        <span class="keyword">return</span> sun.misc.Hashing.stringHash32((String) k);</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    h ^= k.hashCode();</div><div class="line"></div><div class="line">    <span class="comment">// This function ensures that hashCodes that differ only by</span></div><div class="line">    <span class="comment">// constant multiples at each bit position have a bounded</span></div><div class="line">    <span class="comment">// number of collisions (approximately 8 at default load factor).</span></div><div class="line">    h ^= (h &gt;&gt;&gt; <span class="number">20</span>) ^ (h &gt;&gt;&gt; <span class="number">12</span>);</div><div class="line">    <span class="keyword">return</span> h ^ (h &gt;&gt;&gt; <span class="number">7</span>) ^ (h &gt;&gt;&gt; <span class="number">4</span>);</div><div class="line">&#125;</div></pre></td></tr></table></figure>
<h3 id="查找数据"><a href="#查找数据" class="headerlink" title="查找数据"></a>查找数据</h3><figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div><div class="line">30</div><div class="line">31</div><div class="line">32</div></pre></td><td class="code"><pre><div class="line"><span class="comment">/**</span></div><div class="line"> * 根据指定的key查找对应的value</div><div class="line"> * key 可以为null</div><div class="line"> *</div><div class="line"> */</div><div class="line"><span class="function"><span class="keyword">public</span> V <span class="title">get</span><span class="params">(Object key)</span> </span>&#123;</div><div class="line">    <span class="keyword">if</span> (key == <span class="keyword">null</span>)</div><div class="line">        <span class="keyword">return</span> getForNullKey(); <span class="comment">// 查找key为null的value</span></div><div class="line">    Entry&lt;K,V&gt; entry = getEntry(key);</div><div class="line"></div><div class="line">    <span class="keyword">return</span> <span class="keyword">null</span> == entry ? <span class="keyword">null</span> : entry.getValue();</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="comment">/**</span></div><div class="line"> * 根据指定的key查找对应的value</div><div class="line"> */</div><div class="line"><span class="function"><span class="keyword">final</span> Entry&lt;K,V&gt; <span class="title">getEntry</span><span class="params">(Object key)</span> </span>&#123;</div><div class="line">    <span class="keyword">if</span> (size == <span class="number">0</span>) &#123;</div><div class="line">        <span class="keyword">return</span> <span class="keyword">null</span>;</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="keyword">int</span> hash = (key == <span class="keyword">null</span>) ? <span class="number">0</span> : hash(key); <span class="comment">// 计算hash值</span></div><div class="line">    <span class="keyword">for</span> (Entry&lt;K,V&gt; e = table[indexFor(hash, table.length)]; <span class="comment">// 变量数组hash位置的链表</span></div><div class="line">         e != <span class="keyword">null</span>;</div><div class="line">         e = e.next) &#123;</div><div class="line">        Object k;</div><div class="line">        <span class="keyword">if</span> (e.hash == hash &amp;&amp;</div><div class="line">            ((k = e.key) == key || (key != <span class="keyword">null</span> &amp;&amp; key.equals(k))))</div><div class="line">            <span class="keyword">return</span> e; <span class="comment">// 返回value</span></div><div class="line">    &#125;</div><div class="line">    <span class="keyword">return</span> <span class="keyword">null</span>;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
<h3 id="扩容机制"><a href="#扩容机制" class="headerlink" title="扩容机制"></a>扩容机制</h3><p>当HashMap中的元素越来越多的时候,hash的冲突几率也会越来越高，应为数组的长度是固定的16。不进行扩容的话会出现拉链过长的情况导致进行<code>get()</code>数据的时候效率变得非常低,所以HashMap会对数组进行扩容。</p>
<p>这时候HashMap最消耗性能的情况就来了,原数组的全部数据都必须通过<code>transfer()</code>全部重新计算放入新数组</p>
<p>那么什么情况下HashMap才会进行扩容呢？</p>
<p>当HashMap的元素个数超过数组<code>size&gt;size*loadFactor</code>如默认数组大小16,当<code>size &gt; (16*0.07=12)</code>时会将数组扩大至原来的2倍</p>
<p>如果要保证HashMap获取元素的效率建议利用空间换效率,在定义HashMap时将loadFactor设置的小一点,或者直接定义数组的长度,可以明显的提高HashMap的效率</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div><div class="line">30</div><div class="line">31</div><div class="line">32</div><div class="line">33</div><div class="line">34</div><div class="line">35</div></pre></td><td class="code"><pre><div class="line"><span class="comment">/**</span></div><div class="line"> * 设置HashMap的数组长度为两倍并从新计算hash值赋值到新数组中</div><div class="line"> */</div><div class="line"><span class="function"><span class="keyword">void</span> <span class="title">resize</span><span class="params">(<span class="keyword">int</span> newCapacity)</span> </span>&#123;</div><div class="line">    Entry[] oldTable = table;</div><div class="line">    <span class="keyword">int</span> oldCapacity = oldTable.length;</div><div class="line">    <span class="keyword">if</span> (oldCapacity == MAXIMUM_CAPACITY) &#123;</div><div class="line">        threshold = Integer.MAX_VALUE;</div><div class="line">        <span class="keyword">return</span>;</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    Entry[] newTable = <span class="keyword">new</span> Entry[newCapacity];</div><div class="line">    transfer(newTable, initHashSeedAsNeeded(newCapacity));</div><div class="line">    table = newTable;</div><div class="line">    threshold = (<span class="keyword">int</span>)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + <span class="number">1</span>);</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="comment">/**</span></div><div class="line"> * 转移所有元素从当前的数组到新数组</div><div class="line"> */</div><div class="line"><span class="function"><span class="keyword">void</span> <span class="title">transfer</span><span class="params">(Entry[] newTable, <span class="keyword">boolean</span> rehash)</span> </span>&#123;</div><div class="line">    <span class="keyword">int</span> newCapacity = newTable.length;</div><div class="line">    <span class="keyword">for</span> (Entry&lt;K,V&gt; e : table) &#123;</div><div class="line">        <span class="keyword">while</span>(<span class="keyword">null</span> != e) &#123;</div><div class="line">            Entry&lt;K,V&gt; next = e.next;</div><div class="line">            <span class="keyword">if</span> (rehash) &#123;</div><div class="line">                e.hash = <span class="keyword">null</span> == e.key ? <span class="number">0</span> : hash(e.key);</div><div class="line">            &#125;</div><div class="line">            <span class="keyword">int</span> i = indexFor(e.hash, newCapacity);</div><div class="line">            e.next = newTable[i];</div><div class="line">            newTable[i] = e;</div><div class="line">            e = next;</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
<h3 id="fail-fast机制"><a href="#fail-fast机制" class="headerlink" title="fail-fast机制"></a>fail-fast机制</h3><p>HashMap也同样实现了fail-fast机制。</p>
<h3 id="遍历方式"><a href="#遍历方式" class="headerlink" title="遍历方式"></a>遍历方式</h3><p>初始化数据<br><figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div></pre></td><td class="code"><pre><div class="line">  <span class="keyword">private</span> HashMap&lt;Integer, Integer&gt; map = <span class="keyword">new</span> HashMap&lt;&gt;();</div><div class="line"><span class="meta">@Before</span></div><div class="line"></div><div class="line">  <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">data</span><span class="params">()</span> </span>&#123;</div><div class="line">      <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; <span class="number">1000</span>; i++) &#123;</div><div class="line">          map.put(i, i);</div><div class="line">      &#125;</div><div class="line"></div><div class="line"></div><div class="line">  &#125;</div></pre></td></tr></table></figure></p>
<p>根据<code>entrySet()</code>获取HashMap的<code>key-value</code>Set集合遍历<br><figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div></pre></td><td class="code"><pre><div class="line">    <span class="meta">@Test</span></div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">entrySet</span><span class="params">()</span> <span class="keyword">throws</span> Exception </span>&#123;</div><div class="line">        <span class="keyword">for</span> (Map.Entry&lt;Integer, Integer&gt; entry : map.entrySet()) &#123;</div><div class="line">            System.out.println(<span class="string">"Key = "</span> + entry.getKey() + <span class="string">", Value = "</span> + entry.getValue());</div><div class="line">        &#125;</div><div class="line">&#125;</div></pre></td></tr></table></figure></p>
<p>根据<code>keySet()</code>获取HashMap的<code>key</code>Set集合遍历<br><figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div></pre></td><td class="code"><pre><div class="line">    <span class="meta">@Test</span></div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">keySet</span><span class="params">()</span> <span class="keyword">throws</span> Exception </span>&#123;</div><div class="line">        <span class="keyword">for</span> (Integer key : map.keySet()) &#123;</div><div class="line"></div><div class="line">            System.out.println(<span class="string">"Key = "</span> + key + <span class="string">", Value = "</span> + map.get(key));</div><div class="line"></div><div class="line">        &#125;</div><div class="line">&#125;</div></pre></td></tr></table></figure></p>
<p>根据<code>values()</code>获取HashMap的collection集合遍历<br><figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div></pre></td><td class="code"><pre><div class="line"><span class="meta">@Test</span></div><div class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">values</span><span class="params">()</span> <span class="keyword">throws</span> Exception </span>&#123;</div><div class="line">    Integer value = <span class="keyword">null</span>;</div><div class="line"></div><div class="line">    Iterator iterator= map.values().iterator();</div><div class="line">    <span class="keyword">while</span> (iterator.hasNext()) &#123;</div><div class="line">        value = (Integer)iterator.next();</div><div class="line"></div><div class="line">        System.out.println(<span class="string">"Value = "</span> + value);</div><div class="line">    &#125;</div><div class="line">&#125;</div></pre></td></tr></table></figure></p>
<hr>
<h2 id="总结"><a href="#总结" class="headerlink" title="总结"></a>总结</h2><p>要问我阅读HashMap源码的收获,那就是我今天了解一个人</p>
<p><a href="http://baike.baidu.com/item/Doug%20Lea" target="_blank" rel="external">Doug Lea</a></p>
<p>Java界大牛,Collections就是他编写的,并且util.concurrent并发包也是他编写的,非常佩服他</p>
<p>HashMap的扩容操作效率非常非常低,在有大量数据时,初始化HashMap时应估算其大小,避免频繁的扩容</p>
<p>HashMap是非线程安全的,在迭代时如果有其他线程修改值,会触发fail-fast抛出异常</p>
<p>HashMap的计算index值使用的优化取余操作可以应用到其他场景</p>
<p>JDk1.8对于HashMap进行了重构,在单个链表节点大于8时会转换成红黑树来存储,大大提高了大量数据查找时的速度,有时间会去仔细研究下</p>
<hr>
<h2 id="著作权声明"><a href="#著作权声明" class="headerlink" title="著作权声明"></a>著作权声明</h2><p>本文首次发布于 <a href="http://binux.cn">Binux Blog</a>，转载请保留以上链接</p>

    

    
</div>


                

                <!-- Post Comments -->
                
                    




    <!-- 使用 DISQUS_CLICK -->
    <div id="disqus-comment">	
        <div id="disqus_thread"></div>
<!-- include js -->
<script src="/js/ripple.js"></script>

<!-- add animation -->
<style>
        .ripple-container {
        }
        .ripple-container .ripple{
            background-color: rgba(255,255,255,0.4);
            animation: ripple 2s forwards cubic-bezier(0, 0, 0.2, 1);
        }
        @keyframes ripple {
            0% {
                transform: scale(0);
                opacity: 1;
            }
            80% {
                transform: scale(1);
            }
            100% {
                opacity: 0;
            }
        }
		.disqus_click_btn {
            background-color: dodgerblue;
            color: white;
            padding: 10px 20px;
            border:0;
            font-size: 14px;
            cursor: pointer
        }
</style>
	
<!-- add data-ripple attribute -->
<div class="btn_click_load"> 
    <button class="disqus_click_btn" data-ripple>阅读评论 「请确保 disq.us &amp; disquscdn.com &amp; disqus.com 可以正常加载」</button>
</div>
	
<script>
    // add effect to elements
    Array.prototype.forEach.call(document.querySelectorAll('[data-ripple]'), function(element){
        // find all elements and attach effect
        new RippleEffect(element); // element is instance of javascript element node
    });
</script>

<script>
    $('.btn_click_load').click(function() {  //click to load comments
        var disqus_config = function () {
            this.page.url = 'http://binux.cn/2017/03/14/HastMap-Source-Code/index.html';  // Replace PAGE_URL with your page's canonical URL variable
            this.page.identifier = PAGE_IDENTIFIER; // Replace PAGE_IDENTIFIER with your page's unique identifier variable
        };
        (function() { // DON'T EDIT BELOW THIS LINE
            var d = document;
            var s = d.createElement('script');
            s.src = '//xubinux.disqus.com/embed.js';
            s.setAttribute('data-timestamp', + new Date());
            (d.head || d.body).appendChild(s);
        })();
        $('.btn_click_load').css('display','none');
    });
</script>
  	

    </div>
    <style>
        #disqus-comment{
            background-color: #eee;
            padding: 2pc;
        }
    </style>

                
            </div>

            <!-- Post Prev & Next Nav -->
            <nav class="material-nav mdl-color-text--grey-50 mdl-cell mdl-cell--12-col">
    <!-- Prev Nav -->
    
        <a href="/2017/03/15/Spring-Framework/" id="post_nav-newer" class="prev-content">
            <button class="mdl-button mdl-js-button mdl-js-ripple-effect mdl-button--icon mdl-color--white mdl-color-text--grey-900" role="presentation">
                <i class="material-icons">arrow_back</i>
            </button>
            &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
            新篇
        </a>
    

    <!-- Section Spacer -->
    <div class="section-spacer"></div>

    <!-- Next Nav -->
    
        <a href="/2017/03/13/Stack-Source-Code/" id="post_nav-older" class="next-content">
            旧篇
            &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
            <button class="mdl-button mdl-js-button mdl-js-ripple-effect mdl-button--icon mdl-color--white mdl-color-text--grey-900" role="presentation">
                <i class="material-icons">arrow_forward</i>
            </button>
        </a>
    
</nav>

        </div>
    </div>



                    
                        <!-- Overlay For Active Sidebar -->
<div class="sidebar-overlay"></div>

<!-- Material sidebar -->
<aside id="sidebar" class="sidebar sidebar-colored sidebar-fixed-left" role="navigation">
    <div id="sidebar-main">
        <!-- Sidebar Header -->
        <div class="sidebar-header header-cover" style="background-image: url(http://on2bs9q7q.bkt.clouddn.com/sidebar_header.png);">
    <!-- Top bar -->
    <div class="top-bar"></div>

    <!-- Sidebar toggle button -->
    <button type="button" class="sidebar-toggle mdl-button mdl-js-button mdl-js-ripple-effect mdl-button--icon" style="display: initial;" data-upgraded=",MaterialButton,MaterialRipple">
        <i class="material-icons">clear_all</i>
        <span class="mdl-button__ripple-container">
            <span class="mdl-ripple">
            </span>
        </span>
    </button>

    <!-- Sidebar Avatar -->
    <div class="sidebar-image">
        <img src="http://on2bs9q7q.bkt.clouddn.com/avatar.jpg" alt="Binux's avatar">
    </div>

    <!-- Sidebar Email -->
    <a data-toggle="dropdown" class="sidebar-brand" href="#settings-dropdown">
        xu.binux@gmail.com
        <b class="caret"></b>
    </a>
</div>


        <!-- Sidebar Navigation  -->
        <ul class="nav sidebar-nav">
    <!-- User dropdown  -->
    <li class="dropdown">
        <ul id="settings-dropdown" class="dropdown-menu">
            
                <li>
                    <a href="Mailto:xu.binux@gmail.com?Subject=网友来信（来自博客）" target="_blank" title="Email Me">
                        
                            <i class="material-icons sidebar-material-icons sidebar-indent-left1pc-element">email</i>
                        
                        Email Me
                    </a>
                </li>
            
        </ul>
    </li>

    <!-- Homepage -->
    
        <li id="sidebar-first-li">
            <a href="/" target="_self">
                
                    <i class="material-icons sidebar-material-icons">home</i>
                
                主页
            </a>
        </li>
        
    

    <!-- Archives  -->
    
        <li class="dropdown">
            <a href="#" class="ripple-effect dropdown-toggle" data-toggle="dropdown">
                
                    <i class="material-icons sidebar-material-icons">inbox</i>
                
                    归档
                <b class="caret"></b>
            </a>
            <ul class="dropdown-menu">
            <li>
                <a class="sidebar_archives-link" href="/archives/2017/05/">五月 2017<span class="sidebar_archives-count">2</span></a></li><li><a class="sidebar_archives-link" href="/archives/2017/04/">四月 2017<span class="sidebar_archives-count">1</span></a></li><li><a class="sidebar_archives-link" href="/archives/2017/03/">三月 2017<span class="sidebar_archives-count">17</span></a></li><li><a class="sidebar_archives-link" href="/archives/2017/02/">二月 2017<span class="sidebar_archives-count">3</span></a>
            </ul>
        </li>
        
    

    <!-- Categories  -->
    
        <li class="dropdown">
            <a href="#" class="ripple-effect dropdown-toggle" data-toggle="dropdown">
                
                    <i class="material-icons sidebar-material-icons">chrome_reader_mode</i>
                
                分类
                <b class="caret"></b>
            </a>
            <ul class="dropdown-menu">
                <li>
                <a class="sidebar_archives-link" href="/categories/Bug/">Bug<span class="sidebar_archives-count">3</span></a></li><li><a class="sidebar_archives-link" href="/categories/安装教程/">安装教程<span class="sidebar_archives-count">8</span></a></li><li><a class="sidebar_archives-link" href="/categories/工具/">工具<span class="sidebar_archives-count">1</span></a></li><li><a class="sidebar_archives-link" href="/categories/源码分析/">源码分析<span class="sidebar_archives-count">7</span></a></li><li><a class="sidebar_archives-link" href="/categories/随记/">随记<span class="sidebar_archives-count">3</span></a></li><li><a class="sidebar_archives-link" href="/categories/面试题/">面试题<span class="sidebar_archives-count">1</span></a>
            </ul>
        </li>
        
            <li class="divider"></li>
        
    

    <!-- Pages  -->
    
        <li>
            <a href="/about" title="About ME">
                
                    <i class="material-icons sidebar-material-icons">person</i>
                
                About ME
            </a>
        </li>
        
    
        <li>
            <a href="/portfolio" title="Portfolio">
                
                    <i class="material-icons sidebar-material-icons">reorder</i>
                
                Portfolio
            </a>
        </li>
        
    
        <li>
            <a href="/gallery" title="Gallery">
                
                    <i class="material-icons sidebar-material-icons">photo</i>
                
                Gallery
            </a>
        </li>
        
    
        <li>
            <a href="/tags" title="Tags">
                
                    <i class="material-icons sidebar-material-icons">bookmark</i>
                
                Tags
            </a>
        </li>
        
    
        <li>
            <a href="/links" title="Links">
                
                    <i class="material-icons sidebar-material-icons">people</i>
                
                Links
            </a>
        </li>
        
            <li class="divider"></li>
        
    

    <!-- Article Number  -->
    
        <li>
            <a href="/archives">
                文章总数
                <span class="sidebar-badge">23</span>
            </a>
        </li>
        
    
</ul>


        <!-- Sidebar Footer -->
        <!--
I'm glad you use this theme, the development is no so easy, I hope you can keep the copyright, I will thank you so much.
If you still want to delete the copyrights, could you still retain the first one? Which namely "Theme Material"
It will not impact the appearance and can give developers a lot of support :)

很高兴您使用并喜欢该主题，开发不易 十分谢谢与希望您可以保留一下版权声明。
如果您仍然想删除的话 能否只保留第一项呢？即 "Theme Material"
它不会影响美观并可以给开发者很大的支持和动力。 :)
-->

<!-- Sidebar Divider -->


<!-- Theme Material -->

    <a href="https://github.com/viosey/hexo-theme-material"  class="sidebar-footer-text-a" target="_blank">
        <div class="sidebar-text mdl-button mdl-js-button mdl-js-ripple-effect sidebar-footer-text-div" data-upgraded=",MaterialButton,MaterialRipple">
            主题 - Material
            <span class="sidebar-badge badge-circle">i</span>
        </div>
    </a>


<!-- Help & Support -->
<!--

-->

<!-- Feedback -->
<!--

-->

<!-- About Theme -->
<!--

-->

    </div>

    <!-- Sidebar Image -->
    

</aside>

                    

                    
                        <!-- Footer Top Button -->
                        <div class="toTop-wrap">
    <a href="#top" class="toTop">
        <i class="material-icons footer_top-i">expand_less</i>
    </a>
</div>

                    

                    <!--Footer-->
<footer class="mdl-mini-footer" id="bottom">
    
        <!-- Paradox Footer Left Section -->
        <div class="mdl-mini-footer--left-section sns-list">
    <!-- Twitter -->
    

    <!-- Facebook -->
    

    <!-- Google + -->
    

    <!-- Weibo -->
    
        <a href="http://weibo.com/xubin0830" target="_blank">
            <button class="mdl-mini-footer--social-btn social-btn" style="background-image: url(/img/footer/footer_ico-weibo.png);">
                <span class="visuallyhidden">Weibo</span>
            </button><!--
     --></a>
    

    <!-- Instagram -->
    

    <!-- Tumblr -->
    

    <!-- Github -->
    
        <a href="https://github.com/xubinux" target="_blank">
            <button class="mdl-mini-footer--social-btn social-btn" style="background-image: url(/img/footer/footer_ico-github.png);">
                <span class="visuallyhidden">Github</span>
            </button><!--
     --></a>
    

    <!-- LinkedIn -->
    

    <!-- Zhihu -->
    
        <a href="https://www.zhihu.com/people/binux-29/" target="_blank">
            <button class="mdl-mini-footer--social-btn social-btn" style="background-image: url(/img/footer/footer_ico-zhihu.png);">
                <span class="visuallyhidden">Zhihu</span>
            </button><!--
     --></a>
    

    <!-- Bilibili -->
    

    <!-- Telegram -->
    
</div>


        <!--Copyright-->
        <div id="copyright">
            Copyright&nbsp;©&nbsp;
            <script type="text/javascript">
                var fd = new Date();
                document.write(fd.getFullYear());
            </script>
            &nbsp;Binux Blog
        </div>

        <!-- Paradox Footer Right Section -->

        <!--
        I am glad you use this theme, the development is no so easy, I hope you can keep the copyright.
        It will not impact the appearance and can give developers a lot of support :)

        很高兴您使用该主题，开发不易，希望您可以保留一下版权声明。
        它不会影响美观并可以给开发者很大的支持。 :)
        -->

        <div class="mdl-mini-footer--right-section">
            <div>
                <div class="footer-develop-div">Powered by <a href="https://hexo.io" target="_blank" class="footer-develop-a">Hexo</a></div>
                <div class="footer-develop-div">Theme - <a href="https://github.com/viosey/hexo-theme-material" target="_blank" class="footer-develop-a">Material</a></div>
            </div>
        </div>
    
</footer>


                    <!-- Import File -->
<script src="/js/lazyload.min.js"></script>
<script src="/js/js.min.js"></script>
<script src="/js/nprogress.js"></script>

<script type="text/javascript">
    NProgress.configure({
        showSpinner: true
    });
    NProgress.start();
    $('#nprogress .bar').css({
        'background': '#29d'
    });
    $('#nprogress .peg').css({
        'box-shadow': '0 0 10px #29d, 0 0 15px #29d'
    });
    $('#nprogress .spinner-icon').css({
        'border-top-color': '#29d',
        'border-left-color': '#29d'
    });
    setTimeout(function() {
        NProgress.done();
        $('.fade').removeClass('out');
    }, 800);
</script>



    <script src="/js/smoothscroll.js"></script>





    <!-- Busuanzi -->
    <script src="https://dn-lbstatics.qbox.me/busuanzi/2.3/busuanzi.pure.mini.js"></script>







<!-- Swiftye -->


<!-- Local Search-->

    <script>
    var searchFunc = function(path, search_id, content_id) {
        'use strict';
        $.ajax({
            url: path,
            dataType: 'xml',
            success: function( xmlResponse ) {
                // get the contents from search data
                var datas = $( 'entry', xmlResponse ).map(function() {
                    return {
                        title: $( 'title', this ).text(),
                        content: $('content',this).text(),
                        url: $( 'url' , this).text()
                    };
                }).get();
                var $input = document.getElementById(search_id);
                var $resultContent = document.getElementById(content_id);
                $input.addEventListener('input', function() {
                    var str='<ul class=\"search-result-list\">';
                    var keywords = this.value.trim().toLowerCase().split(/[\s\-]+/);
                    $resultContent.innerHTML = '';
                    if (this.value.trim().length <= 0) {
                        return;
                    }
                    // perform local searching
                    datas.forEach(function(data) {
                        var isMatch = true;
                        var content_index = [];
                        var data_title = data.title.trim().toLowerCase();
                        var data_content = data.content.trim().replace(/<[^>]+>/g,'').toLowerCase();
                        var data_url = data.url;
                        var index_title = -1;
                        var index_content = -1;
                        var first_occur = -1;
                        // only match artiles with not empty titles and contents
                        if(data_title !== '' && data_content !== '') {
                            keywords.forEach(function(keyword, i) {
                                index_title = data_title.indexOf(keyword);
                                index_content = data_content.indexOf(keyword);
                                if( index_title < 0 && index_content < 0 ) {
                                    isMatch = false;
                                } else {
                                    if (index_content < 0) {
                                        index_content = 0;
                                    }
                                    if (i === 0) {
                                        first_occur = index_content;
                                    }
                                }
                            });
                        }
                        // show search results
                        if (isMatch) {
                            str += '<li><a href="'+ data_url +'" class="search-result-title" target="_blank">'+ data_title;
                            var content = data.content.trim().replace(/<[^>]+>/g, '');
                            if (first_occur >= 0) {
                                // cut out characters
                                var start = first_occur - 6;
                                var end = first_occur + 6;
                                if (start < 0) {
                                    start = 0;
                                }
                                if (start === 0) {
                                    end = 10;
                                }
                                if (end > content.length) {
                                    end = content.length;
                                }
                                var match_content = content.substr(start, end);
                                // highlight all keywords
                                keywords.forEach(function(keyword) {
                                    var regS = new RegExp(keyword, 'gi');
                                    match_content = match_content.replace(regS, '<em class="search-keyword">'+keyword+'</em>');
                                })
                                str += '<p class="search-result">' + match_content + '...</p>' +'</a>';
                            }
                        }
                    });
                    $resultContent.innerHTML = str;
                });
            }
        });
    }
</script>


    <script>
        var inputArea = document.querySelector('#search');
        var getSearchFile = function() {
            var path = 'search.xml';
            searchFunc(path, 'search', 'local-search-result');
        }

        if(inputArea) {
            inputArea.onfocus = function() {
                getSearchFile();
            }
        }
    </script>


<!-- Window Load-->
<script>
    $(window).load(function() {
        // Post_Toc parent position fixed
        $('.post-toc-wrap').parent('.mdl-menu__container').css('position', 'fixed');
    });
</script>

<!-- MathJax Load-->


                </main>
            </div>
        </body>
    
</html>
